#include <string>
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:
    int longestValidParentheses(string s)
    {
        int len = s.size();
        vector<int> dp(len, 0);
        for (int i = 1; i < len; i++)
        {
            if (s[i] == ')')
            {
                if (s[i - 1] == '(')
                {
                    dp[i] = (i > 1 ? dp[i - 2] : 0) + 2;
                }
                else if (s[i - 1] == ')' && i - dp[i - 1] > 0 && s[i - 1 - dp[i - 1]] == '(')
                {
                    dp[i] = dp[i - 1] + 2 + (i - 2 - dp[i - 1] > 0 ? dp[i - 2 - dp[i - 1]] : 0);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < len; i++)
        {
            if (ans < dp[i])
            {
                ans = dp[i];
            }
        }
        return ans;
    }
};
int main(int argc, char const *argv[])
{

    // Solution s;

    // cout << s.longestValidParentheses(")");
    return 0;
}
